package lucky.xiong.dataStructure.heap;

/**
 * 最大堆
 * 使用数组存储二叉堆
 * 数字仅代表数组下标
 * 1
 * |  |
 * 2   3
 * | |  | |
 * 4 5  6 7
 *
 * @param <T> 需要重写Comparable方法
 * @author xiongjianlin
 */
public class MaxHeap<T extends Comparable> extends Heap<T>{


    public MaxHeap(int capacity) {
        //这里加1是指原来能装的元素个数，那去掉0位，只能装capacity个元素
        data = (T[]) new Comparable[capacity+1];
        count = 0;
    }
    /**
     * 向一个最大堆中添加元素，称为 shift up。
     * <a href="https://www.runoob.com/data-structures/heap-shift-up.html">堆的 shift up</a>
     * @param k 待添加的元素
     */
    private void shiftUp(int k) {
        /**
         * k > 1: 检查当前索引k是否大于1。这是因为根节点（堆顶元素）的索引为1，其没有父节点，所以当k等于1时，说明已经到达堆顶，无需再继续调整。
         * 这个条件确保了循环仅在处理非根节点时进行。
         *
         * data[k/2].compareTo(data[k]) < 0: 比较当前节点（索引为k）与其父节点（索引为k/2，由于堆通常从索引1开始，
         * 父节点索引为子节点索引除以2取整）的值。由于这是一个最大堆，要求父节点的值大于或等于其所有子节点的值。
         * 因此，如果data[k/2].compareTo(data[k]) < 0，即当前节点的值大于其父节点的值，那么堆的性质就被破坏，需要进行调整。
         */
        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    /**
     * 取出根节点后，填补最大堆
     * <a href="https://www.runoob.com/data-structures/heap-shift-down.html">从最大堆中取出一个元素</a>
     * @param k 待调整的节点
     */
    private void shiftDown(int k) {
        // 将k 下挪。先比较2个子节点与自身的大小，将大的子节点替换为根节点

        /**
         * 这一行代码确定了循环的范围。2*k表示当前节点k的左子节点的下标，count表示堆中元素的数量。
         * 当2*k不再小于等于count时，意味着已遍历到叶子节点或不存在的节点，此时不需要再进行下移操作。
         * 因此，该循环确保了对节点k及其所有子节点的遍历。
         */
        while( 2*k <= count ){
            // 默认j=左子节点较大
            int j = 2*k; // 在此轮循环中,data[k]和data[j]交换位置
            // 如果右子节点存在，且右子节点较大，则替换为右子节点
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 ){
                //  j+1 指向右子节点 ； j+1 <= count 表示右节点存在
                // data[j+1].compareTo(data[j]) > 0 :  右大于左
                j ++;
            }
            // 如果当前节点大于等于其左右子节点，则堆的性质保持不变，退出循环
            if( data[k].compareTo(data[j]) >=0 ){
                break;
            }
            swap(k,j);
            k = j;
        }
        System.out.println("shiftDown结束");
    }

    /**
     * 向堆中添加元素
     * @param item 待添加的元素
     * @return -1 堆已满
     */
    public int insert(T item) {
        if (count + 1 >= size()){
            return -1;
        }
        data[++count] = item;
        shiftUp(count);
        return 1;
    }

    /**
     * 获取堆顶元素
     * @return 最大元素，即根节点
     */
    public T getMax(){
        assert count > 0;
        return data[1];
    }

    /**
     * 取出最大元素，并重新排列堆
     * @return 最大元素，即根节点
     */
    public T extractMax(){
        assert count > 0;
        T max = data[1];
        // 将最后一位先移到根节点，最后一位元素会在insert时放新节点，然后shiftUp
        swap(1, count);
        count -- ;
        // 堆根节点重排
        shiftDown(1);
        return max;
    }






    /**
     * run
     */
    public static void main(String[] args) {
        int N = 10; // 堆中元素个数
        int M = 10; // 堆中元素取值范围[0, M)
        MaxHeap<Integer> maxHeap = new MaxHeap<>(N);
        System.out.println(maxHeap.size());


        for( int i = 0 ; i < N ; i ++ ){
            maxHeap.insert( new Integer((int)(Math.random() * M)) );
        }
        System.out.println(maxHeap.size());
        System.out.println("初始化最大堆：" + maxHeap);

        Integer[] arr = new Integer[N];
        // 将最大堆中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = maxHeap.extractMax();
            System.out.print(arr[i] + " ");
            System.out.println("当前堆：" + maxHeap);
        }
        // 确保arr数组是从大到小排列的
        for( int i = 1 ; i < N ; i ++ ){
            assert arr[i-1] >= arr[i];
        }
    }
}
